package leetcode.bit;


import java.util.Arrays;

/**
 * 位集 Bitset 是一种能以紧凑形式存储位的数据结构。

请你实现 Bitset 类。

Bitset(int size) 用 size 个位初始化 Bitset ，所有位都是 0 。
void fix(int idx) 将下标为 idx 的位上的值更新为 1 。如果值已经是 1 ，则不会发生任何改变。
void unfix(int idx) 将下标为 idx 的位上的值更新为 0 。如果值已经是 0 ，则不会发生任何改变。
void flip() 翻转 Bitset 中每一位上的值。换句话说，所有值为 0 的位将会变成 1 ，反之亦然。
boolean all() 检查 Bitset 中 每一位 的值是否都是 1 。如果满足此条件，返回 true ；否则，返回 false 。
boolean one() 检查 Bitset 中 是否 至少一位 的值是 1 。如果满足此条件，返回 true ；否则，返回 false 。
int count() 返回 Bitset 中值为 1 的位的 总数 。
String toString() 返回 Bitset 的当前组成情况。注意，在结果字符串中，第 i 个下标处的字符应该与 Bitset 中的第 i 位一致。


示例：

输入
["Bitset", "fix", "fix", "flip", "all", "unfix", "flip", "one", "unfix", "count", "toString"]
[[5], [3], [1], [], [], [0], [], [], [0], [], []]
输出
[null, null, null, null, false, null, null, true, null, 2, "01010"]

解释
Bitset bs = new Bitset(5); // bitset = "00000".
bs.fix(3);     // 将 idx = 3 处的值更新为 1 ，此时 bitset = "00010" 。
bs.fix(1);     // 将 idx = 1 处的值更新为 1 ，此时 bitset = "01010" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "10101" 。
bs.all();      // 返回 False ，bitset 中的值不全为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "00101" 。
bs.flip();     // 翻转每一位上的值，此时 bitset = "11010" 。
bs.one();      // 返回 True ，至少存在一位的值为 1 。
bs.unfix(0);   // 将 idx = 0 处的值更新为 0 ，此时 bitset = "01010" 。
bs.count();    // 返回 2 ，当前有 2 位的值为 1 。
bs.toString(); // 返回 "01010" ，即 bitset 的当前组成情况。


提示：

1 <= size <= 105
0 <= idx <= size - 1
至多调用 fix、unfix、flip、all、one、count 和 toString 方法 总共 105 次
至少调用 all、one、count 或 toString 方法一次
至多调用 toString 方法 5 次
 */

public class LeetCode2166_Bitset {
    /**
     * 每个int 32bit位
     * 连起来从右开始往右数，第几位就是数字多少，比如下标16的bit位是1，则表示16
     */
    int[] bitset;

    int size;

    // 1 的个数
    int ones;
    // 初始化n个位，所有位都是0
    public LeetCode2166_Bitset(int size) {
        this.size = size;
        bitset = new int[(size / 32) + 1];
        Arrays.fill(bitset, 0);
    }

    // 将下标i的位上的值更新为1
    public void fix(int idx) {
        int arrIndex = idx / 32;
        int bitIndex = idx % 32;

        if ((bitset[arrIndex] & (1 << (31 - bitIndex))) == 0) {
            ones++;
        }

        bitset[arrIndex] |= (1 << (31 - bitIndex));
    }

    // 将下标i的位上的值更新为0
    public void unfix(int idx) {
        int arrIndex = idx / 32;
        int bitIndex = idx % 32;

        int p = bitset[arrIndex] & (1 << (31 - bitIndex));
        if (p > 0) {
            bitset[arrIndex] ^= (1 << (31 - bitIndex));
            ones--;
        }
    }

    // 翻转所有位的值
    public void flip() {
        for (int i = 0; i < bitset.length; i++) {
            bitset[i] = ~bitset[i];
        }
        ones = this.size - ones;
    }

    // 是否所有位都是1
    public boolean all() {
        return ones == size;
    }

    // 是否至少有一位是1
    public boolean one() {
        return ones > 0;
    }

    // 返回所有位中1的数量
    public int count() {
        return ones;
    }

    // 返回所有位的状态
    public String toString() {
        StringBuilder r = new StringBuilder();
        for (int p : bitset) {
            for (int j = 31; j >= 0; j--) {
                r.append((p & (1 << j)) == 0 ? 0 : 1);
            }
        }
        return r.toString();
    }
    
    public static void main(String[] args){
        LeetCode2166_Bitset bitset = new LeetCode2166_Bitset(32);
        bitset.fix(0);
        bitset.fix(1);
        bitset.fix(25);
        
        bitset.unfix(1);
        bitset.unfix(2);
        
        System.out.println("bitset.toString() = " + bitset.toString());
        System.out.println("bitset.one() = " + bitset.one());
        System.out.println("bitset.count() = " + bitset.count());
    }
}